package cn.zifangsky.graph;

import cn.zifangsky.hashtable.Map;
import cn.zifangsky.hashtable.SeparateChainHashTable;
import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;

import java.text.MessageFormat;
import java.util.List;

/**
 * 最大流问题
 *
 * @author zifangsky
 * @date 2019/1/30
 * @since 1.0.0
 */
public class MaxFlow {
    private GraphMatrix graphMatrix;

    public MaxFlow(GraphMatrix graphMatrix) {
        this.graphMatrix = graphMatrix;
    }

    /**
     * 使用 Ford-Fulkerson算法 求最大流问题
     * <p>实现思路：</p>
     * <ul>1. 每次通过深度优先搜索查找一条从起始顶点到结束顶点的路径（即增广路径）</ul>
     * <ul>2. 找出该路径最小流量的边，此流量为该路径能够通过的最大流量</ul>
     * <ul>3. 更新图中的邻接矩阵，上面求得路径上的所有边减去上面求得路径的最大流量</ul>
     * <ul>4. 重复上面三个步骤，直到找不到增广路径为止</ul>
     * <ul>5. 最后所有增广路径的流量之和为给定起始顶点到结束顶点的最大流量</ul>
     * @author zifangsky
     * @date 2019/1/30 13:45
     * @since 1.0.0
     */
    public void fordFulkerson(String startNode, String endNode){
        //图中的顶点数
        int vertexNum = graphMatrix.getVertexNum();
        //所有顶点
        List<String> vertexList = graphMatrix.getVertexList();
        //邻接矩阵
        int[][] matrix = graphMatrix.getMatrix();

        //1. 获取起始和结束顶点在图中的位置
        int startIndex = vertexList.indexOf(startNode);
        int endIndex = vertexList.indexOf(endNode);
        if(startIndex < 0){
            throw new RuntimeException(MessageFormat.format("起始顶点不在图中：{0}", startNode));
        }
        if(endIndex < 0){
            throw new RuntimeException(MessageFormat.format("结束顶点不在图中：{0}", startNode));
        }

        //2. 使用深度优先搜索查找从起始顶点到结束顶点的访问路径（增广路径）
        Node path;
        //最大流量
        int maxFlow = 0;
        do {
            //标识每个顶点是否被访问
            boolean[] visited = new boolean[vertexNum];
            for(int i = 0; i < vertexNum; i++){
                visited[i] = false;
            }

            //2.1 找到一条增广路径
            path = this.dfs(visited, vertexNum,startIndex, endIndex, matrix);

            if(path != null){
                //2.2 找到这条路径的最大流量，并输出路径
                int flow = 0;
                Node temp = path;

                flow = temp.weight;
                System.out.print("Path: " + vertexList.get(temp.startIndex));

                while (temp != null){
                    System.out.print(" --> " + vertexList.get(temp.endIndex));

                    //取路径上最小权重的边为这条路径的流量
                    if(flow > temp.weight){
                        flow = temp.weight;
                    }

                    temp = temp.next;
                }

                maxFlow += flow;
                System.out.print(",Flow: " + flow + "\n");

                //2.3 更新邻接矩阵中的边的权重
                temp = path;
                while (temp != null){
                    int restWeight = temp.weight - flow;

                    //如果某条边没有剩余流量，则去除那条边
                    if(restWeight == 0){
                        matrix[temp.startIndex][temp.endIndex] = -1;
                    }
                    //否则更新该边的权重
                    else{
                        matrix[temp.startIndex][temp.endIndex] = restWeight;
                    }

                    temp = temp.next;
                }
            }
        }while (path != null);

        System.out.println(MessageFormat.format("起始顶点：{0}，结束顶点：{1}，最大流量：{2}"
                , startNode, endNode, maxFlow));
    }

    /**
     * DFS（深度优先搜索）
     */
    private Node dfs(boolean[] visited, int vertexNum,int startIndex, int endIndex, int[][] matrix){
        visited[startIndex] = true;

        //遍历当前顶点的相邻顶点
        for(int j = 0; j < vertexNum; j++){
            //存在边，并且相邻顶点没有被访问过
            if(matrix[startIndex][j] > 0 && !visited[j]){
                Node node = new Node(startIndex, j, matrix[startIndex][j]);
                //如果已经找到结束顶点，则开始返回路径信息
                if(j == endIndex){
                    return node;
                }
                //否则继续遍历后续顶点
                else{
                    Node childNode = this.dfs(visited, vertexNum, j, endIndex, matrix);
                    if(childNode != null){
                        node.next = childNode;
                        return node;
                    }
                }
            }
        }

        return null;
    }


    /**
     * 使用 Edmonds–Karp算法 求最大流问题
     * <p>实现思路：</p>
     * <p>实现思路跟 Ford-Fulkerson 算法类似，但是不同的是 Edmonds–Karp 算法每次都会通过宽度优先搜索查找到一条最短增广路径，然后再进行后续处理</p>
     * @author zifangsky
     * @date 2019/1/31 11:08
     * @since 1.0.0
     */
    public void edmondsKarp(String startNode, String endNode){
        //图中的顶点数
        int vertexNum = graphMatrix.getVertexNum();
        //所有顶点
        List<String> vertexList = graphMatrix.getVertexList();
        //邻接矩阵
        int[][] matrix = graphMatrix.getMatrix();

        //1. 获取起始和结束顶点在图中的位置
        int startIndex = vertexList.indexOf(startNode);
        int endIndex = vertexList.indexOf(endNode);
        if(startIndex < 0){
            throw new RuntimeException(MessageFormat.format("起始顶点不在图中：{0}", startNode));
        }
        if(endIndex < 0){
            throw new RuntimeException(MessageFormat.format("结束顶点不在图中：{0}", startNode));
        }

        //2. 使用宽度优先搜索查找从起始顶点到结束顶点的访问路径（倒序的增广路径）
        Node path;
        //最大流量
        int maxFlow = 0;
        do {
            //2.1 找到一条增广路径（倒序）
            path = this.bfs(vertexNum,startIndex, endIndex, matrix);

            if(path != null){
                //路径流量
                int flow = path.weight;

                //2.2 逆置路径以及找到这条路径的最大流量
                Node nextNode;
                Node temp = null;
                while (path != null){
                    //取路径上最小权重的边为这条路径的流量
                    if(flow > path.weight){
                        flow = path.weight;
                    }

                    //逆置
                    nextNode = path.next;
                    path.next = temp;
                    temp = path;
                    path = nextNode;
                }

                maxFlow += flow;

                //2.3 更新邻接矩阵中的边的权重
                path = temp;
                System.out.print("Path: " + vertexList.get(temp.startIndex));
                while (temp != null){
                    System.out.print(" --> " + vertexList.get(temp.endIndex));

                    int restWeight = temp.weight - flow;

                    //如果某条边没有剩余流量，则去除那条边
                    if(restWeight == 0){
                        matrix[temp.startIndex][temp.endIndex] = -1;
                    }
                    //否则更新该边的权重
                    else{
                        matrix[temp.startIndex][temp.endIndex] = restWeight;
                    }

                    temp = temp.next;
                }
                System.out.print(",Flow: " + flow + "\n");
            }
        }while (path != null);

        System.out.println(MessageFormat.format("起始顶点：{0}，结束顶点：{1}，最大流量：{2}"
                , startNode, endNode, maxFlow));
    }

    /**
     * BFS（宽度优先搜索）
     */
    private Node bfs(int vertexNum,int startIndex, int endIndex, int[][] matrix){
        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
        }
        //定义一个队列
        Queue<Integer> queue = new LinkQueue<>();
        queue.push(startIndex);

        //定义一个Map，用于存储遍历过程中每个顶点从起始顶点到该顶点的路径（逆序）
        Map<Integer, Node> nodeMap = new SeparateChainHashTable<>();

        //1. 如果队列不为空，则一直遍历
        loop : while (!queue.isEmpty()){
            //2. 出队，获取顶点
            int vertexIndex = queue.pop();
            //3. 标识改顶点已经被访问
            visited[vertexIndex] = true;

            //4. 遍历当前顶点的相邻节点
            for(int j = 0; j < vertexNum; j++){
                //5. 如果存在边，并且相邻顶点没有被访问过，则将之加入到队列中
                if(matrix[vertexIndex][j] > 0 && !visited[j]){
                    Node node = new Node(vertexIndex, j, matrix[vertexIndex][j]);
                    //将该顶点添加到队列中
                    queue.pushIfNotExist(j);
                    //从Map中获取上一条边
                    Node previousNode = nodeMap.get(vertexIndex);

                    if(previousNode == null){
                        nodeMap.put(j, node);
                    }else{
                        //如果上一条边存在，并且这个顶点还未被访问过，则将上一条边挂载在当前边的后面，并存储到Map中
                        if(!nodeMap.containsKey(j)){
                            node.next = previousNode;
                            nodeMap.put(j, node);
                        }
                    }

                    //6. 如果已经找到结束顶点，则退出循环，返回路径信息
                    if(j == endIndex){
                        break loop;
                    }
                }
            }
        }

        return nodeMap.get(endIndex);
    }

    /**
     * 表示图中的边信息
     */
    class Node{
        /**
         * 起始顶点的索引
         */
        private int startIndex;
        /**
         * 结束顶点的索引
         */
        private int endIndex;
        /**
         * 边的权重（无向图的边的权重为1）
         */
        private int weight;
        /**
         * 相邻的下一条边
         */
        private Node next;

        public Node(int startIndex, int endIndex, int weight) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.weight = weight;
        }
    }

}
